typedef int ElemType;

//算法思想
//折半查找
void SerachExchangeInsert(ElemType A[], int size, ElemType x) {
    int left = 0;
    int right = size - 1;
    int mid;
    while(left <= right) {
        mid = (left + right) / 2;
        if (A[mid] == x) {
            break;
        }
        if (A[mid] > x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (A[mid] == x && mid != size - 1) {
        ElemType t = A[mid];
        A[mid] = A[mid + 1];
        A[mid + 1] = t;
    }
    if (left > right) {
        int i;
        for(i = size - 1; i < right; i --) {
            A[i + 1] = A[i];
        }
        A[i + 1] = x;
    }
}